#include "DynamicBitset.h"
#include <cmath> /* for log2 */

//#include <string.h> /* for memset */

#include <iostream>

/* Note: the actual bits in each block will be in reverse order (i.e., bit[0] will be in the lsb
	(this will reduce calculations when accessing a bit).
	As long as we access the bitset using the methods, everything should be fine.. */

DynamicBitset::DynamicBitset(const size_t setLength) : 
		blockSize(sizeof(Block) * 8),
		indexShift(log2(blockSize)),
		inBlockMask((1UL << (indexShift + 1)) - 1),
		length(setLength), 
		blocksNumber((length / blockSize) + 1), 
		setBits(0),
		blocks(new Block[blocksNumber]()) // will also initialize the bits to 0 (as with calloc)
{
}

DynamicBitset::~DynamicBitset()
{
	delete[] blocks;
}


void DynamicBitset::set(size_t index)
{
/*	std::cout << "in set, index=" << index << " and block number " << (index / blockSize) << " and inside=" << ((blockSize - (index % blockSize)) - 1) << std::endl;
	blocks[index / blockSize] = 
		(blocks[index / blockSize] | (1 << ((blockSize - (index % blockSize)) - 1)));
*/
	uint blockI = index >> indexShift;
	blocks[blockI] = (blocks[blockI] | (1UL << (index & inBlockMask)));
	setBits++;
}

bool DynamicBitset::test(size_t index) const
{
/*	return (blocks[index / blockSize] & (1 << ((blockSize - (index % blockSize)) - 1)));
*/
//	return (blocks[index / blockSize] & (1UL << (index % blockSize)));
	return (blocks[index >> indexShift] & (1UL << (index & inBlockMask)));
}

inline size_t DynamicBitset::size() const
{
	return length;
}

inline size_t DynamicBitset::getBlockSize() const
{
	return blockSize;
}

inline void DynamicBitset::setBlock(size_t blockNum, Block newBlock)
{
	blocks[blockNum] = newBlock;
}

inline size_t DynamicBitset::getSetBitsNum() const
{
	return setBits;
}

size_t DynamicBitset::getNextSetBit(size_t fromIndex) const
{
	uint blockI = fromIndex >> indexShift;
	Block blockTrail = blocks[blockI] >> (fromIndex & inBlockMask);
	if (blockTrail == 0)
	{
		// If there is no bit in the first block from "fromIndex"
		while ((blocks[blockI] == 0) && (blockI < blocksNumber))
			blockI++;
		if (blockI == blocksNumber)
			return (size_t)-1;
		// find the first bit in the given block
		for (int i = 0; i < blockSize; i++)
		{
			if ((blocks[blockI] & (1UL << i)))
				return (blockI << indexShift) + i;
		}
	}
	else
	{
		// There is a bit in the first block from "fromIndex"
		for (int i = 0; i < blockSize; i++)
		{
			if ((blockTrail & (1UL << i)))
				return fromIndex + i;
		}
	}
	return (size_t)-1;
}

#ifdef DEBUG
#include <iostream>

void DynamicBitset::printBitset() const
{
	for (size_t i = 0; i < length; i++)
	{
		std::cout << ((test(i) == true) ? "1" : "0");
		if ((i + 1) % 81 == 0)
			std::cout << std::endl;
	}
	std::cout << std::endl;
}
#endif /* DEBUG */

